package com.gjx.leetcode;

import java.util.ArrayList;
import java.util.List;

//93. 复原IP地址
//
//给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。
//
//示例:
//
//输入: "25525511135"
//输出: ["255.255.11.135", "255.255.111.35"]

public class Solution093 {
	public List<String> restoreIpAddresses(String s) {
        List<String> res = new ArrayList<>();
        dfs(s, 0, 0, res, "");
        return res;
    }
	
	private void dfs(String s, int start, int part, List<String> res, String path) {
		
		if (start == s.length() && part == 4) {
			res.add(path);
			return;
		} else if (part > 4) {
			return;
		}
		
		for (int i=start; i<s.length() && i<start+3; i++) {
			
			String cur = s.substring(start, i+1);
			if (validIp(cur)) {
				
				String temp = null;
				if (path.length() == 0) {
					temp = cur;
				} else {
					temp = path + '.' + cur;
				}
				
				dfs(s, i+1, part+1, res, temp);
				
			} else {
				break;
			}
			
		}
	}
	
	private boolean validIp(String s) {
		if (s == null || s.length() == 0 || s.length() > 3) {
			return false;
		}
		
		if (s.length() > 1 && s.charAt(0) == '0') {
			return false;
		}
		if (Integer.valueOf(s) > 255) {
			return false;
		}
		return true;
	}
}
